//
// Created by Win10 on 2022/10/16.
//

#include "dl_list.h"
#include<iostream>

using namespace std;

bool InitDLinkList(DLinkList &L) {
    L = (DNode *) malloc(sizeof(DNode));
    if (L == nullptr) {
        return false;
    }
    L->prior = nullptr;
    L->next = nullptr;
    return true;
}

bool empty(DLinkList L) {
    if (L->next == nullptr) {
        return true;
    }
    return false;
}

DNode *GetElem(DLinkList L, int i) {
    if (i < 0) return nullptr;
    int j = 0;
    DNode *p = L;
    while (p != nullptr && j < i) {
        p = p->next;
        j++;
    }
    return p;
}

DNode *LocateElem(DLinkList L, ElemType e) {
    DNode *p = L;
    if (p == nullptr) return nullptr;
    p = p->next;
    while (p != nullptr && p->data != e) {
        p = p->next;
    }
    return p;
}

bool InsertNextDNode(DNode *p, DNode *s) {
    if (p == nullptr || s == nullptr) {
        return false;
    }
    s->next = p->next;
    if (p->next != nullptr)
        p->next->prior = s;
    s->prior = p;
    p->next = s;
    return true;
}

bool InsertNextDNode(DNode *p, ElemType e) {
    if (p == nullptr) return false;
    auto *q = (DNode *) malloc(sizeof(DNode));
    if (q == nullptr) return false;
    q->data = e;
    q->next = nullptr;
    q->prior = p;
    if (p->next != nullptr) {
        p->next->prior = q;
        q->next = p->next;
    }
    p->next = q;
    return true;
}

bool InsertPriorDnode(DNode *p, DNode *s) {
    return InsertNextDNode(p->prior, s);
}

bool InsertDLinkList(DLinkList &L, int i, ElemType e) {
    if (i <= 0) return false;
    DNode *p = GetElem(L, i - 1);
    return InsertNextDNode(p, e);
}

bool DeleteNextNode(DNode *p) {
    if (p == nullptr) return false;
    DNode *q = p->next;
    if (q == nullptr) return false;
    p->next = q->next;
    if (q->next != nullptr) q->next->prior = p;
    free(q);
    return true;
}

bool DestoryList(DLinkList &L) {
    while (L->next != nullptr) {
        DeleteNextNode(L);
    }
    free(L);
    L = nullptr;
    return true;
}

DLinkList List_TailInsert(DLinkList &L) {
    InitDLinkList(L);
    DNode *p = L;
    ElemType x;
    while (cin >> x) {
        InsertNextDNode(p, x);
        p = p->next;
    }
    return L;
}

DLinkList List_HeadInsert(DLinkList &L) {
    InitDLinkList(L);
    ElemType x;
    while (cin >> x) {
        InsertNextDNode(L, x);
    }
    return L;
}

int Length(DLinkList L) {
    DNode *p = L;
    int len = 0;
    while (p->next != nullptr) {
        len++;
        p = p->next;
    }
    return len;
}

bool DeleteNode(DNode *s) {
    DNode *p;
    p = s->prior;
    p->next = s->next;
    if (s->next != nullptr) {
        s->next->prior = p;
    }
    free(s);
    return true;
}

bool ListDelete(DLinkList &L, int i, ElemType &e) {
    if (i <= 0 || i > Length(L)) return false;
    DNode *s;
    s = GetElem(L, i);
    if (s == nullptr) return false;
    e = s->data;
    return DeleteNode(s);
}

void print(DLinkList L) {
    DNode *p = L->next;
    while (p != nullptr) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

void testDLinkList() {
    DLinkList L;
    //cout << "头插法" << endl;
    //List_HeadInsert(L);
    //print(L);
    cout << "尾插法" << endl;
    List_TailInsert(L);
    print(L);
    cout << "长度：" << Length(L) << endl;
    cout << "第1个元素为：" << GetElem(L, 1)->data << endl;
    cout << "第5个元素为：" << GetElem(L, 5)->data << endl;
    cout << "在第一个位置插入元素0" << endl;
    InsertDLinkList(L, 1, 0);
    print(L);
    cout << "在最后一个位置插入元素6" << endl;
    InsertDLinkList(L, 7, 6);
    print(L);

    int e;
    ListDelete(L, 1, e);
    cout << "删除第一个节点：" << e << endl;
    cout << "当前链表为" << endl;
    print(L);

    ListDelete(L, 6, e);
    cout << "删除最后一个节点：" << e << endl;
    cout << "当前链表为" << endl;
    print(L);

    DestoryList(L);
}


int main() {

    testDLinkList();
    return 0;
}